package algorithmExample.Heap;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: zhangrongqing
 * @Date: 2019/11/13 11:08
 */
public class UglyNumber2 {
    public List<Integer> listUglyNumber = new ArrayList<>();

    public int nthUglyNumber(int n) {
        int idx_a = 0, idx_b = 0, idx_c = 0;
        if (n == 1) {
            return 1;
        }
        listUglyNumber.add(1);
        for (int i = 1; i < n; i++) {
            Integer value = listUglyNumber.get(idx_a) * 2;
            Integer value2 = listUglyNumber.get(idx_b) * 3;
            Integer value3 = listUglyNumber.get(idx_c) * 5;
            Integer min = Math.min(value, Math.min(value2, value3));
            listUglyNumber.add(min);
            if (value.equals(min)) {
                idx_a++;
            }
            if (value2.equals(min)) {
                idx_b++;
            }
            if (value3.equals(min)) {
                idx_c++;
            }
        }
        return listUglyNumber.get(n - 1);
    }

    public static void main(String[] args) {
        Integer result = new UglyNumber2().nthUglyNumber(50);
        System.out.println("result : " + result);
    }
}
